import java.util.Stack;

public class Day15 {
    // 最小栈
    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(512);
        minStack.push(-1024);
        minStack.push(-1024);
        minStack.push(512);
        minStack.pop();
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.getMin());
    }


    // 有效的括号
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        int index = 0;
        char[] left = {'(', '[', '{'};
        char[] right = {')', ']', '}'};
        for(char ch : s.toCharArray()) {
            if((index = getIndex(left, ch)) != -1) {
                stack.push(ch);
            } else if((index = getIndex(right, ch)) != -1) {
                if(stack.isEmpty() || getIndex(left, stack.peek()) != index) return false;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }

    private int getIndex(char[] types, char type) {
        for(int i = 0; i < types.length; i++) {
            if(types[i] == type) return i;
        }
        return -1;
    }
}

// 最小栈
class MinStack {
    Stack<Integer> total;// 存放全部的元素
    Stack<Integer> min;// 存放最小值

    public MinStack() {
        total = new Stack<>();
        min = new Stack<>();
    }

    public void push(int val) {
        total.push(val);
        if(min.isEmpty() || min.peek() >= val) {
            min.push(val);
        }
    }

    public void pop() {
        // 注意要用 equals 不然这个只能在 -128~127 之间有用
        if(!total.isEmpty() && min.peek().equals(total.pop())) {
            min.pop();
        }
    }

    public int top() {
        if(!total.isEmpty()) return total.peek();
        return -1;
    }

    public int getMin() {
        if(!total.isEmpty()) return min.peek();
        return -1;
    }
}